package graph2.weight;

import graph2.Graph;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @Author yuh
 * @Date Created in 上午7:58 2018/4/3
 * @Description 稀疏图 用临接表表示
 */
public class WeightedSparseGraph<Weight extends Number & Comparable> implements WeightedGraph {
    /**
     * 节点
     */
    private int v;
    /**
     * 边
     */
    private int m;
    /**
     * 矩阵
     */
    private LinkedList<Edge>[] matrix;
    /**
     * 是否有向
     */
    private boolean directed;

    public WeightedSparseGraph(int v, boolean directed) {
        this.directed = directed;
        this.v = v;
        this.m = 0;
        matrix = (LinkedList<Edge>[]) new LinkedList[v];
        for (int i = 0; i < matrix.length; i++) {
            matrix[i] = new LinkedList<>();
        }
    }

    /**
     * 几个顶点
     *
     * @return
     */
    @Override
    public int V() {
        return v;
    }

    /**
     * 几条边
     *
     * @return
     */
    @Override
    public int E() {
        return m;
    }

    /**
     * 两个顶点之间是否有边
     *
     * @param v
     * @param w
     * @return
     */
    @Override
    public boolean hasEdge(int v, int w) {
        LinkedList<Edge> list = this.matrix[v];
        for (Edge edge : list) {
            if (edge.other(v) == w) {
                return true;
            }
        }
        return false;
    }


    @Override
    public void addEdge(Edge edge) {
        matrix[edge.v()].add(edge);
        if (!directed && edge.v() != edge.w()) {
            matrix[edge.w()].add(edge);
        }
    }

    /**
     * 打印整个连接情况
     */
    @Override
    public void show() {
        for (int i = 0; i < matrix.length; i++) {
            LinkedList<Edge> list = this.matrix[i];
            System.out.println(i + "->" + list);
        }

    }

    /**
     * 这个顶点关联的所有的边
     *
     * @param v
     * @return
     */
    @Override
    public Iterable<Edge> adj(int v) {
       return matrix[v];
    }
}
